using System;
using System.Collections.Generic;
using System.Text;

namespace MiniBall
{
    public class Miniball
    {

        // data members
        private List<double[]> points;         // STL list keeping the points
        private Basis basis;              // basis keeping the current ball
        private int supportEnd;    // past-the-end iterator of support set

        private int dimensions;

        public Miniball(int dim)
        {
            dimensions = dim;

            points = new List<double[]>();
            basis = new Basis(dimensions);
            supportEnd = 0;
        }

        public Miniball(int dim, IEnumerable<double[]> points)
        {
            dimensions = dim;

            this.points = new List<double[]>();
            foreach (double[] p in points)
                this.points.Add(p);

            basis = new Basis(dimensions);
            supportEnd = 0;
        }

        public List<double[]> Points
        {
            get { return points; }
        }

        public void Build(bool pivoting)
        {
            basis.Reset();
            supportEnd = 0;

            if (pivoting)
                PivotMb(points.Count);
            else
                MoveToFrontMb(points.Count);
        }

        private void MoveToFrontMb(int i)
        {
            supportEnd = 0;

            if (basis.Size == dimensions + 1) return;

            for (int k = 0; k < i; )
            {
                int j = k++;

                if (basis.Excess(points[j]) > 0)
                {
                    if (basis.Push(points[j]))
                    {
                        MoveToFrontMb(j);
                        basis.Pop();
                        MoveToFront(j);
                    }
                }
            }
        }

        private void MoveToFront(int j)
        {
            if (supportEnd == j)
                supportEnd++;

            //L.splice (L.begin(), L, j);
            double[] p = points[j];
            points.RemoveAt(j);
            points.Insert(0, p);
        }

        private void PivotMb(int i)
        {
            int t = 1;
            MoveToFrontMb(t);
            double max_e, old_sqr_r = 0;
            do
            {
                int pivot;
                max_e = MaxExcess(t, i, out pivot);
                if (max_e > 0)
                {
                    t = supportEnd;
                    if (t == pivot) ++t;
                    old_sqr_r = basis.SquaredRadius;
                    basis.Push(points[pivot]);
                    MoveToFrontMb(supportEnd);
                    basis.Pop();
                    MoveToFront(pivot);
                }
            } while ((max_e > 0) && (basis.SquaredRadius > old_sqr_r));
        }

        private double MaxExcess(int t, int i, out int pivot)
        {
            double[] c = basis.Center;
            double sqr_r = basis.SquaredRadius;
            double e, max_e = 0;

            pivot = -1;//***

            for (int k = t; k != i; ++k)
            {
                double[] p = points[k];
                e = -sqr_r;
                for (int j = 0; j < p.Length; ++j)
                    e += Sqr(p[j] - c[j]);
                if (e > max_e)
                {
                    max_e = e;
                    pivot = k;
                }
            }
            return max_e;
        }

        private double Sqr(double r)
        {
            return r * r;
        }

        public double[] Center
        {
            get { return basis.Center; }
        }

        public double SquaredRadius
        {
            get { return basis.SquaredRadius; }
        }

        public double Radius
        {
            get { return (double) Math.Sqrt(basis.SquaredRadius); }
        }

        public int SupportPointsCount
        {
            get { return basis.SupportSize; }
        }

        public double Accuracy(out double slack)
        {
            double e, max_e = 0;
            int n_supp = 0;

            foreach (double[] i in points)
            {
                n_supp++;
                if ((e = Math.Abs(basis.Excess(i))) > max_e)
                    max_e = e;
            }

            // you've found a non-numerical problem if the following ever fails
            //assert (n_supp == nr_support_points());

            for (int i = supportEnd; i < points.Count; i++)
                if ((e = basis.Excess(points[i])) > max_e)
                    max_e = e;

            slack = basis.Slack();
            return (max_e / SquaredRadius);
        }

        public bool IsValid(double tolerance)
        {
            double slack;
            return ((Accuracy(out slack) < tolerance) && (slack == 0.0));
        }
    }
}
    
